package org.raymond.iworks.study.basic.algorithm.search;

import java.util.Arrays;

/**
 * @author raymond
 * @version V1.0
 * @Description: 相比二分和插值,计算mid时是加减法,而不是除法
 * 基本介绍:
 * 1) 黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比.
 * 取其前三位数字的近似值是0.618.由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比.
 * 这是一个神奇的数字,会带来意想不到的效果
 * 2) 斐波那契数列{1,1,2,3,5,8,13,21,34,55...},当前数等于前两个数之和.且发现斐波那契数列的两个相邻数的比例,
 * 无限接近黄金分割值:0.618.
 *
 * 斐波那契查找算法原理:
 * 与二分查找和插值查找相似,仅仅改变了中间节点(mid)的位置,mid不再是中间或者插值得到,而是位于黄金分割点附近,即
 * mid=low+F[k-1]-1,(F代表斐波那契数列)
 * 对F[k-1]-1的理解:
 * 1)由斐波那契数列F[k]=F[k-1]+F[k-2]的性质,可以得到(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1.
 * 该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段。从而使中间位置
 * mid=low+F[k-1]-1
 * 想象一条长度为F[k]的线段,前面部分长度为F[k-1],后面部分长度为F[k-2]
 * 由于需要一个mid,因此前面部分线段需要为mid空出一个位置,即前面部分数组长度为F[k-1]-1,
 * 数组下标是从左至右,从low到high的,因此 mid=low+F[k-1]-1
 *
 * 2)类似的,每一子段也可以用相同的方式分割
 * 3)但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1.这里的k值只要能使得F[k]-1恰好
 * 大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可.
 * while(n>fib(k)-1)
 *   k++;
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};

        System.out.println("idx:"+fibSearch(arr, 1001));
    }
    // 因为mid=low+F(k-1)-1,需要使用斐波那契数列,因此我们需要先获取到一个斐波那契数列
    public static int[] fib(int size){
        int[] f = new int[size];
        f[0] = 1;
        f[1] = 1;
        for(int i=2; i<size; i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }

    // 非递归的方式编写算法
    public static int fibSearch(int[] arr, int findVal) {
        int low = 0;
        int high = arr.length - 1;
        // 表示斐波那契分割数值的下标
        int k = 0;
        // 存放mid值
        int mid = 0;
        int f[] = fib(20);
        // 获取到斐波那契分割数值的下标
        // 如果数组的最大值大于斐波那契数列中第k个数的前一个数,则K继续往后移
        while (high > f[k] - 1) {
            k++;
        }
        // 因为f[k]值可能大于a的长度,因此需要使用Arrays类构造一个新的数组,并指向arr[]
        // 不足的部分会使用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 实际上需要使用arr数组最后的数填充temp
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        // 使用while循环,查找findVal,只要满足这个条件,就可以一直查找
        while (low <= high) {
            System.out.println("while...");
            mid = low + f[k - 1] - 1;
            // 如果满足条件,即findVal小于mid位置的值,则继续向数组的前面(左边)查找
            if (findVal < temp[mid]) {
                // 向左查找,即左边界不变,将右边界置为原中间位置的左边一个位置
                high = mid - 1;
                /**
                 * 为什么是k--
                 * 说明:
                 * 1. 全部元素=前面的元素+后面的元素
                 * 2. f[k] = f[k-1] + f[k-2]
                 * 因为前面有f[k-1]个元素,所以可以继续拆分f[k-1]=f[k-2]+f[k-3]
                 * 即在f[k-1]的前面继续查找,需要 k--
                 * 即下次循环mid=low+f[k-1-1]-1
                 */
                k--;
                // 否则,满足此条件就应该向数组的后面(右边)查找
            } else if (findVal > temp[mid]) {
                // 向右查找,即右边界不变,左边界置为原中间位置的右边一个位置
                low = mid + 1;
                /**
                 * 为什么是k-=2
                 * 说明:
                 * 1. 全部元素=前面的元素+后面的元素
                 * 2. f[k] = f[k-1] + f[k-2]
                 * 3. 因为后面有f[k-2]个元素,所以可以继续拆分f[k-2]=f[k-3]+f[k-4]
                 * 4. 即在f[k-2]的前面继续查找 需要 k-=2
                 * 为什么是k-=2
                 * 4.1 想象 f[k-2] 是总线段的右边部分, 即f[k-2]=f[k-3]+f[k-4],
                 * fib数列: {1,1,2,3,5,8}
                 * 4.2 假设k=5,总长度为f[k]=f[5]=8
                 * 则 f[5]=f[k-1]+f[k-2]=5+3;
                 * 左边部分长度f[k-1]=f[4]为5, 右边部分长度f[k-2]=f[3]为3;
                 * 右左的长度f[k-3]=f[2]为2, 右右的长度f[k-4]=f[1]为1;
                 * 4.3 fib数列中,右边线段的长度数值在左边线段的长度数值的前一位,即如果推进到下次循环,
                 * 向左边查找时,k=k-1, 向右边查找时, k=k-2
                 * 5. 即下次循环mid=low+f[k-1-2]-1
                 */
                k -= 2;
            } else {
                // 因为temp可能扩充过,所以mid有可能大于high,所以不能直接返回mid,而是要确定是返回的哪个下标
                // 如果mid还在原来的数组范围内,就直接返回mid,否则需要返回high
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}
